package Sort.面试.腾讯;

/**
 * 给定一个只包含小写字母字符串，每次可以选择两个相同的字符删除，并在字符串结尾新增任意一个小写字母。
 * 请问最少多少次操作后，所有的字母都不相同？
 *
 * 输入例子：
 * "abab"
 * 输出例子：
 *
 * 例子说明：
 * 第一次操作将两个'a'变成一个'f'，字符串变成"bbf"。
 * 第二次操作将两个'b'变成一个'b'，字符串变成"fb"。
 * 操作方式不是唯一的，但可以证明，最少操作次数为2。
 */
public class MinOperations {


    /**
     * 解题思路
     * 1. ===> kind+cnt 是所有字符  cnt+kind-26(超过26的部分有重复要再消除)+cnt（已经操作的次数）
     * 2. ===> 链接：https://ac.nowcoder.com/discuss/1045726?type=0&order=0&page=1&channel=-1
     *      首先cnt是第一次遍历时操作 出现偶数次数的字符 的操作次数，即cnt个任意字符，kinds就是这个过程中剩余的字符数量，
     *      比如说kinds=3，cnt=28，假设是kinds代表abc，那么根据贪心，cnt中可以拿出26-3即23个,记为a个，
     *      来填充没有出现的字符，那么cnt中还剩cnt-a=5个任意字符，至少还要5次，所以一共是cnt+5，即cnt+(cnt-a)；
     * @param str
     * @return
     */
    public static int minOperations(String str){
        int[] nums = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char tempCh = str.charAt(i);
            nums[tempCh - 'a']++;
        }



        // 除数 余数
        int divisor = 0, remainder = 0;
        for (int i = 0; i < 26; i++) {
            divisor += nums[i]/2;  //对应字母需要操作的次数
            remainder += remainder%2; //超过26次，需要重复操作的次数
        }

        if(divisor + remainder <= 26){
            return divisor;
        }else{
            int noAppend = 26 - remainder;  // 第二次 还没有出现字符的个数
            return 2*divisor- noAppend;
        }

    }

    public static void main(String[] args) {
        System.out.println((int) 'z');
//        System.out.println("abab = "+minOperations("abab"));
//        System.out.println("edr = "+minOperations("edr"));
//        System.out.println("f = "+minOperations("f"));
//        System.out.println("dddndi = " +minOperations("dddndi"));
//        System.out.println("lmmcnnn = " +minOperations("lmmcnnn"));
        System.out.println(minOperations("eueyeuvdeoyuveoyvyvecevveocedcddvouvudvuuuoydeucvecdycdodcdcdvecooeecdycycydecuc"));

        String a = "aab";
        System.out.println(a.replaceFirst("00",""));
    }
}
